package math;

import java.util.*;

/**
 * Created by fengliejv on 2017/10/15.
 */
// slide window method is excellent
public class FindAllAnagramsinaString438 {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<>();
        if(s.length()==0){
            return list;
        }

        for(int i=0;i<s.length()-p.length()+1;i++){
            if(isAnagram(s.substring(i,i+p.length()),p)){
                list.add(i);
            }
        }
        return list;
    }


    public boolean isAnagram(String s, String t) {
        int[] alphabet = new int[26];
        for (int i = 0; i < s.length(); i++) alphabet[s.charAt(i) - 'a']++;
        for (int i = 0; i < t.length(); i++) alphabet[t.charAt(i) - 'a']--;
        for (int i : alphabet) if (i != 0) return false;
        return true;
    }
     class Solution {
         public List<Integer> findAnagrams(String s, String t) {
             List<Integer> result = new LinkedList<>();
             if(t.length()> s.length()) return result;
             Map<Character, Integer> map = new HashMap<>();
             for(char c : t.toCharArray()){
                 map.put(c, map.getOrDefault(c, 0) + 1);
             }
             int counter = map.size();

             int begin = 0, end = 0;
             int head = 0;
             int len = Integer.MAX_VALUE;


             while(end < s.length()){
                 char c = s.charAt(end);
                 if( map.containsKey(c) ){
                     map.put(c, map.get(c)-1);
                     if(map.get(c) == 0) counter--;
                 }
                 end++;

                 while(counter == 0){
                     char tempc = s.charAt(begin);
                     if(map.containsKey(tempc)){
                         map.put(tempc, map.get(tempc) + 1);
                         if(map.get(tempc) > 0){
                             counter++;
                         }
                     }
                     if(end-begin == t.length()){
                         result.add(begin);
                     }
                     begin++;
                 }

             }
             return result;
         }

        public List<Integer> slidingWindowTemplateByHarryChaoyangHe(String s, String t) {
            //init a collection or int value to save the result according the question.
            List<Integer> result = new LinkedList<>();
            if(t.length()> s.length()) return result;

            //create a hashmap to save the Characters of the target substring.
            //(K, V) = (Character, Frequence of the Characters)
            Map<Character, Integer> map = new HashMap<>();
            for(char c : t.toCharArray()){
                map.put(c, map.getOrDefault(c, 0) + 1);
            }
            //maintain a counter to check whether match the target string.
            int counter = map.size();//must be the map size, NOT the string size because the char may be duplicate.

            //Two Pointers: begin - left pointer of the window; end - right pointer of the window
            int begin = 0, end = 0;

            //the length of the substring which match the target string.
            int len = Integer.MAX_VALUE;

            //loop at the begining of the source string
            while(end < s.length()){

                char c = s.charAt(end);//get a character

                if( map.containsKey(c) ){
                    map.put(c, map.get(c)-1);// plus or minus one
                    if(map.get(c) == 0) counter--;//modify the counter according the requirement(different condition).
                }
                end++;

                //increase begin pointer to make it invalid/valid again
                while(counter == 0 /* counter condition. different question may have different condition */){

                    char tempc = s.charAt(begin);//***be careful here: choose the char at begin pointer, NOT the end pointer
                    if(map.containsKey(tempc)){
                        map.put(tempc, map.get(tempc) + 1);//plus or minus one
                        if(map.get(tempc) > 0) counter++;//modify the counter according the requirement(different condition).
                    }

                /* save / update(min/max) the result if find a target*/
                    // result collections or result int value

                    begin++;
                }
            }
            return result;
        }
    }
}
